By yusijia

Updated:

Contents
  1. 1. 题意：
  2. 2. 分析：

题意：

　　给定n个电话号码串，问这n个电话号码串中是否存在某一串是其它串的前缀，
如果存在输出NO，否则YES

分析：

　　把这n个电话号码串建立成字典树，在插入的时候我们直接判断当前插入的
字符串是不是其它串的前缀或者其它串是不是这个串的前缀即可

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
//解法一：用动态分配
#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <cstring>

#define N 10

struct node{
    int mark;
    struct node *child[N];
}*root;

void init(struct node **p)
{
    (*p) = new struct node;
    (*p)->mark = 0;
    for(int i = 0; i < N; i++)
        (*p)->child[i] = NULL;
}

bool insert_node(char *str)
{
    int len = strlen(str);
    struct node *p = root;
    bool isOk = false;
    int i;
    for(i = 0; i < len; i++)
    {
        if(p->mark == 1)
            return false; //说明其他字符串时这个字符串的前缀
        if(p->child[str[i] - '0'] == NULL)
        {
            init(&(p->child[str[i] - '0']));
            isOk = true;//如果一直都不是NULL说明前面已经存在这个数字了，到最后如果还是
        }               //没有经过这个步骤,则说明这个字符串是其他字符串的前缀isOk仍然=false
        p = p->child[str[i] - '0'];
    }
    p->mark = 1;
    return isOk;
}

void delete_root(struct node *root)
{
    for(int i = 0; i < N; i++)
    {
        if(root->child[i]!=NULL)
        {
            delete_root(root->child[i]);    //通过递归来释放内存
        }
    }
    delete root;
}

int main()
{
    int n, cas;
    char str[15];
    bool flag;                   //标记
    scanf("%d", &cas);
    while(cas--)
    {
        scanf("%d", &n);
        flag = true;
        init(&root);            //初始化根节点
        while(n--)
        {
            scanf("%s", str);
            if(flag && !insert_node(str))
                flag = false;
        }
        if(flag)
            puts("YES");        //自带回车
        else
            puts("NO");
        delete_root(root);      //必须释放空间，否则会报Memory Limited的错误
    }
    return 0;
}



////////////////////////////////
解法二：静态分配

#include<cstdio>
#include<cstring>
#include<iostream>
#include<algorithm>
using namespace std;

const int MAXN = 1000010;
const int N = 10;

struct Node{
    int mark;
    Node* child[N];
};
Node node[MAXN];  //一开始就开好数组,到后面就不需要动态分配了
Node *root;
int pos;

Node *newNode(){
    node[pos].mark = 0;
    for(int i = 0 ; i < N ; i++)
        node[pos].child[i] = NULL;
    return &node[pos++];
}

bool insert(char *str){
    int len = strlen(str);
    Node *s = root;
    bool isOk = false;
    for(int i = 0 ; i < len ; i++){
        if(s->mark == 1)
            return false;
        int num = str[i]-'0';
        if(s->child[num] == NULL){
            s->child[num] = newNode();
            isOk = true;
        }
        s = s->child[num];
    }
    s->mark = 1;
    return isOk;
}

int main(){
    int cas , n;
    bool ans;
    char str[MAXN];
    scanf("%d" , &cas);
    while(cas--){
       scanf("%d" , &n);
       ans = true;
       pos = 0;
       root = newNode();
       while(n--){
           scanf("%s" , str);
           if(ans && !insert(str))
               ans = false;
       }
       if(ans)
           puts("YES");
       else
           puts("NO");
    }
    return 0;
}
Contents
  1. 1. 题意：
  2. 2. 分析：